package com.bbz.core.sortalgorithm;

/**
 * 类别：交换排序 冒泡排序
 * 
 * 1、基本思想：在要排序的一组数中，对当前还未排好序的范围内的全部数， 自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。
 * 即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换
 * 
 * @author binbin.a.zhang
 *
 */
public class BubbleSort {
	public static void main(String[] args) {
		sort();
		sort1();
	}

	/**
	 * 最基本的冒泡排序
	 */
	private static void sort() {
		int[] a = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1, 8 };
		System.out.println("排序之前：");
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
		int temp = 0;
		// 冒泡排序
		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a.length - i - 1; j++) {
				// 这里-i主要是每遍历一次都把最大的i个数沉到最底下去了，没有必要再替换了
				if (a[j] > a[j + 1]) {
					temp = a[j];
					a[j] = a[j + 1];
					a[j + 1] = temp;
				}
			}
		}
		System.out.println();
		System.out.println("排序之后：");
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}

	}

	/**
	 * 优化升级版冒泡排序
	 * 1:利用布尔变量isSorted作为标记。如果在本轮排序中，元素有交换，则说明数列无序；如果没有元素交换，说明数列已然有序，直接跳出大循环。
	 * 2:在每一轮排序的最后，记录下最后一次元素交换的位置，那个位置也就是无序数列的边界，再往后就是有序区了
	 */
	private static void sort1() {
		int[] a = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1, 8 };
		System.out.println();
		System.out.println("排序之前：");
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
		int temp = 0;
		// 记录最后一次交换的位置
		int lastExchangeIndex = 0;
		// 无序数列的边界，每次比较只需要比到这里为止
		int sortBorder = a.length - 1;
		// 冒泡排序
		for (int i = 0; i < a.length; i++) {

			// 有序标记，每一轮的初始是true
			boolean isSorted = true;
			for (int j = 0; j < sortBorder; j++) {
				// 这里-i主要是每遍历一次都把最大的i个数沉到最底下去了，没有必要再替换了
				if (a[j] > a[j + 1]) {
					temp = a[j];
					a[j] = a[j + 1];
					a[j + 1] = temp;
					// 有元素交换，所以不是有序，标记变为false
					isSorted = false;
					// 把无序数列的边界更新为最后一次交换元素的位置
					lastExchangeIndex = j;
				}
			}
			sortBorder = lastExchangeIndex;
			if (isSorted) {
				break;
			}
		}
		System.out.println();
		System.out.println("排序之后：");
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
	}
}
